#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 500

typedef struct BaseNum
{
    int base;
    int len;
    int a[N];
} BaseNum;

BaseNum cvtfm;
BaseNum cvtto;

int ch2d(char ch)
{
   if(ch >= '0' && ch <= '9')
   {
       return ch - '0';
   }
   else if(ch >= 'A' && ch <= 'Z')
   {
       return ch - 'A' + 10;
   }
   else if(ch >= 'a' && ch <= 'z')
   {
       return ch - 'a' + 36;
   }
   else
   {
       return -1;
   }
}

char d2ch(int n)
{
    if(n >= 0 && n <= 9)
    {
        return n + '0';
    }
    else if(n >= 10 && n <= 35)
    {
        return n - 10 + 'A';
    }
    else if(n >= 36 && n <= 61)
    {
        return n - 36 + 'a';
    }
    else
    {
        return '?';
    }
}

void init()
{
    cvtfm.base = 0;
    cvtfm.len = 0;
    memset(cvtfm.a, 0, sizeof(cvtfm.a[0])*N);
    cvtto.base = 0;
    cvtto.len = 0;
    memset(cvtto.a, 0, sizeof(cvtto.a[0])*N);
}

void basenumshow(BaseNum* bn)
{
    int i = 0;
    printf("%d ", bn->base);
    for(i = bn->len-1; i >= 0; i--)
    {
        printf("%c", d2ch(bn->a[i]));
    }
    printf("\n");
}

void trail(BaseNum* bn)
{
    int i = 0;

    for(i = bn->len-1; i >= 0; i--)
    {
        if(bn->a[i] == 0)
        {
            bn->len--;
        }
        else
        {
            return;
        }
    }
}

void chu(BaseNum* cf, int mod ,int* remainder)
{
    int i = 0;

    *remainder = 0;
    for(i = cf->len-1; i >= 0; i--)
    {
        *remainder = *remainder * cf->base + cf->a[i];
        cf->a[i] = *remainder / mod;
        *remainder %= mod;
    }
    trail(cf);
}


void process()
{
    int r = 0;
    basenumshow(&cvtfm);

    while(1)
    {
        if(cvtfm.len == 0)
        {
            break;
        }
        chu(&cvtfm, cvtto.base, &r);
        //printf("%c\n", d2ch(r));
        cvtto.a[cvtto.len++] = r;
    }
    basenumshow(&cvtto);
    printf("\n");
}

int main()
{
    //freopen("bin\\debug\\in.txt", "r", stdin);
    //freopen("bin\\debug\\out.txt", "w", stdout);

    int n = 0, i = 0, j = 0;
    char line[N] = {'\0'};

    scanf("%d", &n);
    for(i = 0; i < n; i++)
    {
        init();
        scanf("%d%d", &(cvtfm.base), &(cvtto.base));
        scanf("%s", line);
        for(j = strlen(line)-1; j >= 0; j--)
        {
            cvtfm.a[cvtfm.len++] = ch2d(line[j]);
        }

        process();
    }

    return 0;
}
